|
The Chang and Roberts algorithm is a ring-based coordinator election algorithm, employed in distributed computing. == The algorithm == The algorithm assumes that each process has a Unique Identification (UID) and that the processes can arrange themselves in a unidirectional ring with a communication channel going from each process to the clockwise neighbour. The two part algorithm can be described as follows: # Initially each process in the ring is marked as ''non-participant''. # A process that notices a lack of leader starts an election. It creates an ''election message'' containing its UID. It then sends this message clockwise to its neighbour. # Every time a process sends or forwards an ''election message'', the process also marks itself as a participant. # When a process receives an ''election message'' it compares the UID in the message with its own UID. ## If the UID in the election message is larger, the process unconditionally forwards the ''election message'' in a clockwise direction. ## If the UID in the election message is smaller, and the process is not yet a participant, the process replaces the UID in the message with its own UID, sends the updated ''election message'' in a clockwise direction. ## If the UID in the election message is smaller, and the process is already a ''participant'' (i.e., the process has already sent out an election message with a UID at least as large as its own UID), the process discards the election message. ## If the UID in the incoming election message is the same as the UID of the process, that process starts acting as the leader. When a process starts acting as the leader, it begins the second stage of the algorithm. # The leader process marks itself as ''non-participant'' and sends an ''elected message'' to its neighbour announcing its election and UID. # When a process receives an ''elected message'', it marks itself as ''non-participant'', records the elected UID, and forwards the ''elected message'' unchanged. # When the ''elected message'' reaches the newly elected leader, the leader discards that message, and the election is over. Assuming there are no failures this algorithm will finish. The algorithm works for any number of processes N, and does not require any process to know how many processes are in the ring. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chang and Roberts algorithm」の詳細全文を読む スポンサード リンク
|